/*
 * @Author: szx
 * @Date: 2021-11-17 13:20:42
 * @LastEditTime: 2021-11-17 13:54:00
 * @Description:
 * @FilePath: \leetcode\1-99\39\39.js
 */
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */

var combinationSum = function (candidates, target) {
    const ans = [];
    const dfs = (target, combine, idx) => {
        if (idx === candidates.length) {
            return;
        }
        if (target === 0) {
            ans.push(combine);
            return;
        }
        // 直接跳过
        dfs(target, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            dfs(target - candidates[idx], combine.push(candidates[idx]).slice(), idx);
        }
    };
    // [...combine, candidates[idx]]
    dfs(target, [], 0);
    return ans;
};

var combinationSum = function (candidates, target) {
    const n = candidates.length;
    const res = [];

    const dfs = (arr, tar) => {
        for (let i of candidates) {
            const tmp = tar - i;
            console.log(arr, tar, i);
            if (tmp > 0) {
                arr.push(i);
                dfs(arr, tmp);
            } else if (tmp == 0) {
                arr.push(i);
                console.log('??', arr.slice());
                res.push(arr.slice());
                console.log('??', res);
                arr.pop(arr.length - 1);
                return;
            } else {
            }
        }
        arr.pop(arr.length - 1);
    };
    dfs([], target);
    return res;
};
console.log(combinationSum([2, 3, 4], 5));
